Như trong phần đánh giá giải thuật, một trong những nhược điểm lớn của thuật toán Trộn trực tiếp là không tận dụng những thông tin về đặc tính của dãy cần sắp xếp. Ví dụ trường hợp dãy đã có thứ tự sẵn. Chính vì vậy, trong thực tế người ta ít dùng thuật toán trộn trực tiếp mà người ta dùng phiên bản cải tiến của nó. Phiên bản này thường được biết với tên gọi thuật toán trộn tự nhiên (Natural Merge sort).

Khái niệm đường chạy

Ðể khảo sát thuật toán trộn tự nhiên, trước tiên ta cần định nghĩa khái niệm đường chạy (run):

Một đường chạy của dãy số a là một dãy con không giảm của cực đại của a. Nghĩa là, đường chạy r = (ai, ai+1,..., aj) phải thỏa điều kiện:

• 0 ≤ i ≤ j < n, với n là số phần tử của dãy a
• ak ≤ ak+1 ∀k, i ≤ k ≤ j

Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 đường chạy (12); (2, 8); (5); (1, 6); (4, 15).

Giải thuật

Các bước thực hiện thuật toán trộn tự nhiên như sau:

• Bước 1: // Chuẩn bị

r = 0; // r dùng để đếm số đường chạy

• Bước 2:

Tách dãy a1, a2,..., an thành 2 dãy b, c theo nguyên tắc luân phiên từng đường chạy:

• Bước 2.1:

Phân phối cho b một đường chạy; r = r+1;Nếu a còn phần tử chưa phân phốiPhân phối cho c một đường chạy; r = r+1;

• Bước 2.2:

Nếu a còn phần tử: quay lại bước 2.1;

• Bước 3:

Trộn từng cặp đường chạy của 2 dãy b, c vào a.

• Bước 4:

Nếu r >= 2 thì trở lại bước 1;Ngược lại: Dừng;

Ưu và nhược điểm

Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần biết số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điểm dừng của thuật toán vì dãy đã có thứ tự là dãy chi có một đường chạy.

Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. Vì vậy thuật toán trộn thường được dùng để sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file.